package 中等.双指针;

import java.util.Arrays;

/**
 * 给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中
 * spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。
 * 同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大
 * 于等于 success ，那么它们视为一对 成功 的组合。
 * 请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i
 * 个咒语成功组合的 药水 数目。
 */
public class 咒语和药水的成功对数_2300 {

    public static void main(String[] args) {

    }

    /**
     * 排序+二分
     * 将药水的能量强度从小到大排序，找到最小的可以和 spells[i] 成功
     * 组合的索引 idx 那么 potions[j] 及其右边的药水都能成功组合
     */
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int[] ans = new int[spells.length];
        Arrays.sort(potions);

        for (int i = 0; i < spells.length; i++) {

            ans[i] = binarySearch(spells[i], potions, success);

        }

        return ans;
    }

    private int binarySearch(long spell, int[] potions, long success) {
        int pairs = 0;
        int left = 0, right = potions.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (potions[mid] * spell >= success) {
                pairs = potions.length - mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return pairs;
    }

}
